package com.ruoyi.learn.java.algorithm.tree;

import java.util.LinkedList;
import java.util.Queue;

// 二叉树节点定义
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class BinaryTreeBuilder {
    // 从数组构建二叉树
    public static TreeNode buildTree(Integer[] arr) {
        if (arr == null || arr.length == 0 || arr[0] == null) {
            return null;
        }

        // 创建根节点
        TreeNode root = new TreeNode(arr[0]);

        // 使用队列存储待处理的节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int index = 1; // 从数组的第二个元素开始处理

        while (!queue.isEmpty() && index < arr.length) {
            TreeNode current = queue.poll();

            // 处理左孩子
            if (arr[index] != null) {
                current.left = new TreeNode(arr[index]);
                queue.add(current.left);
            }
            index++;

            // 处理右孩子
            if (index < arr.length && arr[index] != null) {
                current.right = new TreeNode(arr[index]);
                queue.add(current.right);
            }
            index++;
        }

        return root;
    }

    // 测试方法：层次遍历打印二叉树
    public static void printTree(TreeNode root) {
        if (root == null) {
            System.out.println("空树");
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");

            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    public static void main(String[] args) {
        // 测试用例
        Integer[] arr = {1, 2, 3, null, 4, null, 5,6,7,8,9,null,10,null,11};
        TreeNode root = buildTree(arr);

        System.out.println("构建的二叉树层次遍历结果：");
        printTree(root); // 输出：1 2 3 4 5
    }
}
